package sword2offer;

/**
 * <p>
 * 复杂链表的复制
 * </p>
 * 请实现 copyRandomList 函数，复制一个复杂链表。在复杂链表中，每个节点除了有一个 next 指针指向下一个节点，还有一个 random 指针指向链表中的任意节点或者 null。
 * @author LovelyBigDuck
 * @date 2022/3/14 20:43
 */

import java.util.HashMap;
import java.util.Map;

/**
 * 思路一：递归回溯+哈希表
 * 思路二：迭代+节点拆分
 */
public class S_035 {
    class Node {
        int val;
        Node next;
        Node random;

        public Node(int val) {
            this.val = val;
            this.next = null;
            this.random = null;
        }
    }
    class Solution {
        // 拷贝完成的送进哈希表里，一一对应关系
        Map<Node, Node> cachedNode = new HashMap<Node, Node>();

        public Node copyRandomList(Node head) {
            if (head == null) {
                return null;
            }
            if (!cachedNode.containsKey(head)) {
                Node headNew = new Node(head.val);
                cachedNode.put(head, headNew);
                headNew.next = copyRandomList(head.next);
                headNew.random = copyRandomList(head.random);
            }
            return cachedNode.get(head);
        }
    }
}
